package main

import "fmt"

/**
 * @param num: a array
 * @param target: a num
 * @return: return all combinations
 *          we will sort your return value in output
 */
func CombinationSet(num []int, target int) []int {
	//dfs
	ans := []int{}
	dfs(num, target, &ans, -1)
	return ans
}

func dfs(arr []int, target int, ans *[]int, parent int) {
	if parent != -1 && parent < target {
		*ans = append(*ans, parent)
	}

	if parent == 0 || parent >= target {
		return
	}

	if parent == -1 {
		parent = 0
	}

	for i := 0; i < len(arr); i++ {
		cur := parent*10 + arr[i]
		dfs(arr, target, ans, cur)
	}
}

func main() {
	fmt.Println(CombinationSet([]int{0, 1, 2, 3}, 30))
}
